I. Introduction
Computer or dam networks, i.e. interconnected collections of autonomous computers, provide a variety of services such as electronic mail and data transfer services. FIG. 1 illustrates the structure of a typical computer network. The first part of the network typically comprises a collection of Machines 102, called hosts, intended for running application programs. The network also includes Communication Subnet 104 linking the hosts. The subnet's job is to carry messages from host to host. The subnet typically comprises two basic components: Routers (also called Switching Elements, Nodes or Interface Message Processors) 106 and Links (also called Transmission Lines) 108. Each host is connected to one, or occasionally several routers. See generally, Andrew S. Tanenbaum, Computer Networks, Prentice Hall, Inc., Englewood Cliffs, N.J., 1981.
The role of routing is to set up paths between nodes of the network for the efficient utilization of network services and for the efficient transfer of data. There are several classes of routing problems, e.g., routing in virtual-circuit networks, routing in datagram networks and routing in shortest-path networks.